1132F - Clear the String - CodeForces Solution

#include <bits/stdc++.h> 
 
#define int long long 
#define pii pair <int,int> 
#define st first 
#define nd second 
#define vi vector <int> 
#define vpii vector <pii> 
#define pb push_back 
#define pf push_front 
#define FOR(a, b, c) for (int i = a; i <= b; i += c) 
#define ROS(a, b, c) for (int i = a; i >= b; i -= c) 
#define lb lower_bound 
#define ub upper_bound 
#define FILE "" 
#define trii pair <int, pii> 
using namespace std;
 
const int oo = 1e18;
const int N = 500 + 9;
const int mod = 1e9 + 7;
const int blocks = 448;
 
int n, k, a[N];
int res, f[N][N];
string s;

int dp(int l, int r) 
{
	int &res = f[l][r];
	if (res != -1) return res;
	if (l > r) return res = 0;
	if (l == r) return res = 1;
	res = dp(l + 1, r) + 1;
	for (int i = l + 1; i <= r; i++) 
	{
		if (s[i] == s[l]) 
		{
			res = min(res, dp(l + 1, i - 1) + dp(i, r));
		}
	}	
	return res;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	//freopen(FILE".inp","r", stdin);
	//freopen(FILE".out","w", stdout);
	cin >> n >> s;
	memset(f, -1, sizeof(f));
	int ans = dp(0, n - 1);
	cout << ans;
	return 0;
}